﻿// Agri-Net POJ - 1258.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>
using namespace std;
//https://vjudge.csgrandeur.cn/problem/POJ-1258

/*
农民约翰当选为镇长！他的竞选承诺之一是为该地区的所有农场提供互联网连接。
当然，他需要您的帮助。
农场主约翰为自己的农场订购了高速网络连接，并打算与其他农场主共享网络连接。
为了最大限度地降低成本，他希望铺设最少的光纤来连接他的农场和其他所有农场。
给定一份清单，列出连接每对农场所需的光纤数量，您必须找出连接所有农场所需的最小光纤数量。
每个农场都必须与其他农场相连，这样数据包才能从任何一个农场流向任何其他农场。
任何两个农场之间的距离都不能超过 100,000。
输入
输入包括多组数据。对于每组数据，第一行包含农场数量 N（3 <= N <= 100）。
下面几行是 N x N 连接矩阵，每个元素表示一个农场到另一个农场的距离。
从逻辑上讲，它们是由 N 个空格分隔的整数组成的 N 行。在物理上，它们的长度限制为 80 个字符，因此有些行会延续到其他行。
当然，对角线将为 0，因为从农场 i 到农场本身的距离对这个问题并不重要。
输出
针对每种情况，输出一个整数长度，即连接整组农场所需的最小光纤长度之和。
样本
输入复制输出复制
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

28
*/

const int N = 105;
const int INF = 0x3f3f3f3f;
int gra[N][N];
int n;
int dist[N];
bool st[N];

int prim() {
	memset(dist, 0x3f, sizeof dist);
	memset(st, false, sizeof st);
	int res = 0;
	for (int i = 0; i < n; i++) {
		int t = -1;
		for (int j = 0; j < n; j++) {
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		}

		if (i && dist[t] == INF) return INF;
		if (i) res += dist[t];
		st[t] = true;

		for (int j = 0; j < n; j++) dist[j] = min(dist[j], gra[t][j]);
	}

	return res;
}


int main()
{
	while (cin >> n) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> gra[i][j];
			}
		}

		cout << prim() << endl;
	}


	return 0;
}

 